//环形链表
import  linkListDefine.ListNode;

import java.util.List;

public class loopLinkList {
    public ListNode loop(ListNode list){
        ListNode fast = list;
        ListNode slow = list;//同一个起点
        while(fast!=null){
            fast = fast.next.next;//两步走
            slow = slow.next;//一步走
            if(slow == fast){//如果相遇了
                slow = list;//慢指针从头开始走
//                while (fast!=null){
//                    if(slow==fast){
//                        return fast;//表示找到了环的入口
//                    }
//                    fast = fast.next;
//                    slow = slow.next;
//                }
                while (fast!=slow){//第一次相遇后，慢指针从链表头开始走，快指针从相遇的位置开始走
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return  null;
    }
    public static void main(String[] args) {
        int[] a = new int[]{1,2,3,4,5,6,7,8,9};
        ListNode list = ListNode.createList(a);
        //创建一个循环链表
        int pos = 3;//表示最后一个结点连接到了下标第2（0序）结点
        ListNode head = list;
        ListNode temp = null;//记录进环的那个结点，方便建立环
        while (head.next!=null){
            head = head.next;
            pos--;
            if(pos==0){
                temp = head;
            }
        }
        head.next = temp;//形成环

        var main = new loopLinkList();
        ListNode res = main.loop(list);
        System.out.println(res.data);
    }
}
